package org.tang.tianchi.notes.array;


import java.util.*;
import java.util.stream.Collectors;

/**
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * <p>
 * 子数组 是数组中的一个连续部分。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出：6
 * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 * 示例 2：
 * <p>
 * 输入：nums = [1]
 * 输出：1
 * 示例 3：
 * <p>
 * 输入：nums = [5,4,-1,7,8]
 * 输出：23
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= nums.length <= 105
 * -104 <= nums[i] <= 104
 * <p>
 * <p>
 * 进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
 */
public class 最大子数组和 {

    public static void main(String[] args) {
        int[] nums = {-2,1};
        System.out.println(maxSubArray(nums));
    }

    public static int maxSubArray(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        Set<Integer> list = new TreeSet<>();

        for (int i = 0; i < nums.length; i++) {
            int sum = nums[i];
            list.add(sum);
            for (int j = i + 1; j < nums.length; j++) {
                // 逐个，第一个数，加第二个数，加第三个数
                sum += nums[j];
                list.add(sum);
                // 找到其中最大的一个数
            }
        }
//        System.out.println(list.toString());
        return list.stream().max(Comparator.comparingInt(o -> o)).get();
    }


    /**
     *
     * 先定第一个数字，如果小于等于0，后移；
     * 然后选择第二个数字，如果小于0，先不加入sum，记录目前的sum.继续往后，每遇到一个数小于0, 记录sum，然后继续往后
     * @param nums
     * @return
     */
    public static int maxSubArray02(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        Set<Integer> list = new TreeSet<>();

        for (int i = 0; i < nums.length; i++) {
            int sum = nums[i];
            list.add(sum);
            for (int j = i + 1; j < nums.length; j++) {
                // 逐个，第一个数，加第二个数，加第三个数
                sum += nums[j];
                list.add(sum);
                // 找到其中最大的一个数
            }
        }
//        System.out.println(list.toString());
        return list.stream().max(Comparator.comparingInt(o -> o)).get();
    }
}
